The invention relates to Field Programmable Gate Arrays (FPGAs). More particularly, the invention relates to a method for synthesizing wide gates into carry logic in an FPGA.
Programmable integrated circuits (ICs) are a well-known type of integrated circuit that may be programmed by a user to perform specified logic functions. (The term xe2x80x9cprogrammable ICsxe2x80x9d as used herein includes but is not limited to FPGAs, mask programmable devices such as Application Specific ICs (ASICs), Programmable Logic Devices (PLDs), and devices in which only a portion of the logic is programmable.) One type of programmable IC, the field programmable gate array (FPGA), typically includes an array of configurable logic blocks (CLBs) surrounded by a ring of programmable input/output blocks (IOBs). The CLBs and IOBs are interconnected by a programmable interconnect structure. The CLBs, IOBs, and interconnect structure are typically programmed by loading a stream of configuration data (bitstream) into internal configuration memory cells that define how the CLBs, IOBs, and interconnect structure are configured. The configuration data may be read from memory (e.g., an external PROM) or written into the FPGA by an external device. The collective states of the individual memory cells then determine the function of the FPGA.
A CLB typically includes one or more function generators (often implemented as lookup tables, or LUTs), and one or more registers that can optionally be used to register the LUT outputs. Some CLBs also include carry logic that is used to implement arithmetic functions such as adders, subtractors, counters, and multipliers. Implementing logic using carry chains can be faster, sometimes much faster, than implementing the equivalent logic in LUTs and passing carry signals from one bit to the next through the interconnect structure. The speed of a carry chain depends on the number of bits in the carry chain and the speed of each carry bit (among other factors). The speed of the equivalent logic implemented as LUTs depends on the number of levels of logic (i.e., the number of LUTs on the slowest path) required to implement the function. Usually, using the carry chain is faster. However, using the carry chain imposes placement constraints because the ordering of portions of the user""s function is set by the carry chain.
Two forms of design entry are common: schematic entry and Hardware Description Languages (HDLs) such as Verilog and VHDL. When schematic entry is used, the designer specifies the exact implementation desired for his circuit. At a higher level, when HDL code is used, the circuit is described by its logical function. Synthesis software then translates the logical function into specific logic targeted for a specified FPGA. Although circuit elements can be manually instantiated in HDL code, this method is avoided since it is labor-intensive and the code can typically only be targeted to a specific programmable IC architecture.
Well-known synthesis tools such as those distributed by Synopsys, Inc., of Mountain View, Calif., recognize arithmetic functions in the HDL code and implement these functions using carry logic. Other functions such as wide logic gates and cascade circuits can also be implemented using carry logic. However, these other types of functions used in HDL code are not so implemented by the synthesis tools, even when the method that is used results in a much slower circuit. It would be desirable, therefore, for synthesis tools to implement logic in a manner that makes better use of the carry structure in order to minimize the delay of the circuit.
According to the invention, logic functions that can be implemented by the carry chain are detected, and if the carry chain implementation is faster than a conventional implementation, the functions are implemented using the carry chain. In the general case, to be implemented in a carry chain, the functions must be of a form that each logic operator operates on the output of a previous portion of the function. That is, the function must be able to be put into the form
F=((( . . . (f0$f1)$f2)$f3) . . . $fn)
where f0 through fn represent portions of the function that can be implemented in a single LUT, and $ represents a logic operator such as AND, OR, XNOR, etc. When implemented in an FPGA having four-input lookup tables, the above form covers a very large number of functions because each of f0 through fn can be any function of four or fewer input values. Further, the $ operators may occur in any order.
The simplest example, very commonly used, is a wide AND function in which the number of inputs is larger than the number of inputs to a single LUT. If software detects a number of inputs greater than a selected threshold, software will implement the function with adjacent LUTs and associated carry multiplexers. The software will assign the AND gate inputs to adjacent lookup tables, will assign a logic 1 to a carry-in input of the carry-chain multiplexer controlled by the first LUT, will assign logic 0 to the independent input of each carry-chain multiplexer being used to implement the AND function, will assign the AND function to each LUT in the chain implementing the function, and will take the wide AND output from the last carry-chain multiplexer implementing the function.
A wide OR gate is implemented similarly. However, each LUT is programed to generate the NOR function, the first carry multiplexer will receive logic 0 on its carry-in input and each carry multiplexer will receive logic 1 on its independent input.
When the software implements a function having mixed operators, it determines the state of the independent carry multiplexer input and the state of the carry-in input from the type of operator that follows.
The above summary of the present invention is not intended to describe each disclosed embodiment of the present invention. The figures and detailed description that follow provide additional example embodiments and aspects of the present invention.